googologywikiaorg-20200223-history
Forum:Question about Rayo's number
I have some questions about Rayo's number and FOST. #How do we define numbers in FOST? Do we use 0={} and a+1=a∪{a}? #How do we know what number a FOST expression defines? #What happens if you define function f(x) in FOST such that f(x) is the smallest natural number greater than all natural numbers that can be uniquely identified by a FOST expression of at most x symbols (which is the same as the definition of Rayo's function)? Does that make Rayo's function above a certain value and Rayo's Number ill-defined because of Berry's paradox? Rpakr (talk) 20:54, April 5, 2018 (UTC) :1. Yes. :2. Of course, in general, there will be no way to determine that - Rayo's function is uncomputable. But in specific cases, we can work out by hand which numbers satisfy the formula. For example, if the formula is (properly formalized version of) "the set has exactly one element and this element has no elements", then we know it defines 1. For a less trivial example, we can write formulas which include definitions of addition or multiplication, or some more complicated functions, and then we will know that the formula defines a value of this function. :3. It's impossible to define this function in FOST, so there is no contradiction. This is the same kind of question as: what happens if we program a Turing machine which computes the Busy Beaver numbers? The thing is that it's impossible to program such a TM. Similarly we can't define your function in FOST. LittlePeng9 (talk) 21:13, April 5, 2018 (UTC) ::3. But why isn't possible to define such function of FOST? "Because it leads to contradiction" should not be the reason because that assumes FOST and Rayo are well-defined. That does not eliminate the possibility of FOST being ill-defined because of Berry's paradox. ::I think you can encode FOST symbol sequence to a natural number and define g(A) where A is a FOST expression and g(A) is the smallest number that satisfies A by making a set that contains all natural numbers and check one by one if n satisfies A or not. Rpakr (talk) 22:58, April 5, 2018 (UTC) :::You cannot define this g(A), because it is not possible to define "n satisfies A", where A is any FOST statement, in FOST. This follows from Tarski's undefinability theorem, which says that any sufficiently strong theory cannot define truth in that theory. :::Of course, in any discussion of whether a function is definable in a given theory, we must assume the well-definedness of that theory. But, you have not given a good reason why we should doubt the well-definedness of FOST, because you have not given a good reason why your g(A) should be definable. Deedlit11 (talk) 00:26, April 6, 2018 (UTC) ::::Can't you define g(A) by: ::::1. N is the set of natural numbers ::::2. Make the FOST statement into reverse Polish notation and encode it to a natural number ::::3. Define f(n,A_2,A_3,A_4,...A_k) where k is the number of variable in the expression as: let 1 be natural number n and m be set A_m. If the expression is true return 1, if not return 0 (To do that you go to the statement, decode it to the RPN version, if you find variable 1 put n, if variable p (p>1) put A_p, if you find AB∈ put true if A∈B else put false, if you find AB= put true if A=B else put false, etc. and reduce it to a "true" or a "false") ::::4. Define g(A) as: if there exists set n, A_2, A_3, A_4,...A_k that satisfies (n∈N, f(n,A_2,A_3,A_4,...A_k) is true) then return true, else return false Rpakr (talk) 00:59, April 6, 2018 (UTC) :::::You have defined g(A), but using English. You cannot define g(A) using the language of FOST, because there is no expression for "A is true". Which is as it should be, because truth is not something we natively associate with languages and theories; only when we attach a model to a theory do we talk about truth, within the model. For Rayo's function, the model we are talking about is V, the cumulative hierarchy. Deedlit11 (talk) 01:17, April 6, 2018 (UTC) ::::::What do you mean by "there is no expression for "A is true""? What do you mean by "attach a model to a theory"? Rpakr (talk) 01:23, April 6, 2018 (UTC) :::::::I'm not sure how to say it better - there is no symbol in FOST that denotes truth. Let's say we define a theory FOSTT, which is FOST, but we have a predicate T(X), such that T(X) is true if and only if the FOSTT statement A that X encodes is true. Then, we can make the standard diagonal argument to make an expression that basically says "This expression is false", and we have a contradiction. So FOSTT is not well-defined. :::::::But, FOST does not have such a truth predicate, so we cannot make such an argument, nor can we make your argument. :::::::I was being casual with "attach a model to a theory"; I just meant a model that satisfies the theory. Normally we talk about truth in a model, not a theory. Of course, we have been talking about truth in a theory here, so we are assuming there is an intended model that the theory was meant to satisfy. I'm just saying this is not standard practice. Deedlit11 (talk) 01:44, April 6, 2018 (UTC) ::::::::"we can make the standard diagonal argument to make an expression that basically says "This expression is false"" I don't know what is "standard diagonal argument". Rpakr (talk) 11:27, April 6, 2018 (UTC) :The truth predicates, Rayo's function (your f) and Rayo's number can all be formally defined in second-order set theory (indeed, Rayo himself did that originally). And in second-order set theory (more specifically, in a theory like Morse-Kelley) we can prove that this function is well-defined, and that it cannot be defined in FOST. :As for the 'there is no expression for "A is true"', this is the content of , which states that in any formal language which can talk about natural numbers, there is no predicate T(n) such that, for every formula x with its Godel number g(x), x is equivalent to T(g(x)). LittlePeng9 (talk) 07:57, April 6, 2018 (UTC) ::So do you mean that it is impossible to make a FOST statement that defines function h(A) where h(A) is equal to true is A is true and h(A) is equal to false when A is false for any FOST statement A? Rpakr (talk) 11:27, April 6, 2018 (UTC) :::Basically, yes. To be specific, we need to consider h(#A), where #A is the Godel number of statement A. LittlePeng9 (talk) 12:58, April 6, 2018 (UTC)